package com.south.base.test.arithmetic.tree;

import com.south.base.test.arithmetic.link.ListNode;
import javafx.util.Pair;

import java.util.*;

/**
 * @author Administrator
 * @date 2020/6/16 10:03
 */
public class BinaryTree {
    /**
     * Encodes a tree to a single string.
     */
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    public void serialize(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append(",");
            return;
        }
        sb.append(root.val).append(",");
        serialize(root.left, sb);
        serialize(root.right, sb);
    }


    /**
     * Decodes your encoded data to tree.
     */
    public TreeNode deserialize(String data) {
        if ("".equals(data)) {
            return null;
        }
        String[] se = data.split(",");
        return deserialize(se, new int[]{0});
    }

    public TreeNode deserialize(String[] s, int[] index) {
        if (s.length - 1 < index[0]) {
            return null;
        }
        if ("".equals(s[index[0]])) {
            index[0]++;
            return null;
        }

        TreeNode root = new TreeNode(Integer.valueOf(s[index[0]++]));
        root.left = deserialize(s, index);
        root.right = deserialize(s, index);
        return root;
    }

    /**
     * 从先序遍历还原二叉树
     * 我们从二叉树的根节点 root 开始进行深度优先搜索。
     * 在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。
     * （如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。
     * 如果节点只有一个子节点，那么保证该子节点为左子节点。
     * 给出遍历输出 S，还原树并返回其根节点 root。
     */
    public TreeNode recoverFromPreOrder(String S) {
        return recoverFromPreOrder(S, new int[]{0}, 0);
    }

    public TreeNode recoverFromPreOrder(String tree, int[] index, int dep) {
        int tmpDep = 0;
        int tmpIndex = index[0];
        for (; tmpIndex < tree.length(); tmpIndex++) {
            if ('-' != tree.charAt(tmpIndex)) {
                break;
            }
            tmpDep++;
        }
        if (tmpDep != dep) {
            return null;
        }
        int num = 0;
        for (; tmpIndex < tree.length(); tmpIndex++) {
            if ('-' == tree.charAt(tmpIndex)) {
                break;
            }
            num = num * 10 + (tree.charAt(tmpIndex) - '0');
        }
        TreeNode treeNode = new TreeNode(num);
        index[0] = tmpIndex;
        treeNode.left = recoverFromPreOrder(tree, index, tmpDep + 1);
        treeNode.right = recoverFromPreOrder(tree, index, tmpDep + 1);
        return treeNode;
    }

    /**
     * 从上到下打印二叉树 II
     * 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        levelOrder(res, root, 0);
        return res;
    }

    public void levelOrder(List<List<Integer>> res, TreeNode node, int dep) {
        if (node == null) {
            return;
        }
        if (res.size() == dep) {
            res.add(new ArrayList<>());
        }
        res.get(dep).add(node.val);
        levelOrder(res, node.left, dep + 1);
        levelOrder(res, node.right, dep + 1);
    }

    /**
     * 二叉树的层次遍历 II
     * 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        levelOrder(res, root, 0);
        Collections.reverse(res);
        return res;
    }

    /**
     * 合并二叉树
     * 你需要将他们合并为一个新的二叉树。
     * 合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，
     * 否则不为 NULL 的节点将直接作为新二叉树的节点。
     */
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        TreeNode treeNode = t1;
        if (t1 != null && t2 != null) {
            treeNode.val = treeNode.val + t2.val;
            treeNode.left = mergeTrees(t1.left, t2.left);
            treeNode.right = mergeTrees(t1.right, t2.right);
        } else if (t2 != null) {
            treeNode = t2;
            return treeNode;
        }
        return treeNode;
    }

    public boolean check(TreeNode p, TreeNode q) {
        return (p == null && q == null) || (p != null && q != null && p.val == q.val);
    }

    /**
     * 相同的树
     * 给定两个二叉树，编写一个函数来检验它们是否相同。
     * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (!check(p, q)) {
            return false;
        }

        ArrayDeque<TreeNode> deqP = new ArrayDeque<>();
        ArrayDeque<TreeNode> deqQ = new ArrayDeque<>();
        deqP.addLast(p);
        deqQ.addLast(q);

        while (!deqP.isEmpty()) {
            p = deqP.removeFirst();
            q = deqQ.removeFirst();

            if (!check(p, q)) {
                return false;
            }
            if (p != null) {
                if (!check(p.left, q.left)) {
                    return false;
                }
                if (p.left != null) {
                    deqP.addLast(p.left);
                    deqQ.addLast(q.left);
                }
                if (!check(p.right, q.right)) {
                    return false;
                }
                if (p.right != null) {
                    deqP.addLast(p.right);
                    deqQ.addLast(q.right);
                }
            }
        }
        return true;
    }

    /**
     * 对称二叉树
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        TreeNode u = root.left;
        TreeNode v = root.right;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(u);
        q.offer(v);
        while (!q.isEmpty()) {
            u = q.poll();
            v = q.poll();
            if (u == null && v == null) {
                continue;
            }
            if ((u == null || v == null) || (u.val != v.val)) {
                return false;
            }

            q.offer(u.left);
            q.offer(v.right);

            q.offer(u.right);
            q.offer(v.left);
        }
        return true;

    }

    /**
     * 二叉树的最大深度
     * 给定一个二叉树，找出其最大深度。
     * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
     * 说明: 叶子节点是指没有子节点的节点。
     */
    public int maxDepth(TreeNode root) {
        Queue<Pair<TreeNode, Integer>> stack = new LinkedList<>();
        if (root != null) {
            stack.add(new Pair(root, 1));
        }

        int depth = 0;
        while (!stack.isEmpty()) {
            Pair<TreeNode, Integer> current = stack.poll();
            root = current.getKey();
            int curDepth = current.getValue();
            if (root != null) {
                depth = Math.max(depth, curDepth);
                stack.add(new Pair(root.left, curDepth + 1));
                stack.add(new Pair(root.right, curDepth + 1));
            }
        }
        return depth;
    }

    /**
     * 将有序数组转换为二叉搜索树
     * 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
     * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(0, nums.length - 1, nums);
    }

    public TreeNode sortedArrayToBST(int left, int right, int[] nums) {
        if (left > right) return null;

        // always choose right middle node as a root
        int p = (left + right) / 2;
        if ((left + right) % 2 == 1) ++p;

        // inorder traversal: left -> node -> right
        TreeNode root = new TreeNode(nums[p]);
        root.left = sortedArrayToBST(left, p - 1, nums);
        root.right = sortedArrayToBST(p + 1, right, nums);
        return root;
    }

    /**
     * 二叉树中的最大路径和
     * 给定一个非空二叉树，返回其最大路径和。
     * 本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
     */
    public int maxPathSum(TreeNode root) {
        return maxGain(root)[1];
    }

    public int[] maxGain(TreeNode node) {
        if (node == null) {
            return new int[]{0, Integer.MIN_VALUE};
        }

        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int[] left = maxGain(node.left);
        int[] right = maxGain(node.right);
        int leftGain = Math.max(left[0], 0);
        int rightGain = Math.max(right[0], 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewPath = node.val + leftGain + rightGain;

        // 更新答案
        int maxSum = Math.max(right[1], Math.max(left[1], priceNewPath));

        // 返回节点的最大贡献值
        return new int[]{node.val + Math.max(leftGain, rightGain), maxSum};
    }

    /**
     * 路径总和
     * 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
     * 说明: 叶子节点是指没有子节点的节点。
     */
    public boolean hasPathSum(TreeNode root, int sum) {
        return dfs(root, sum, 0);
    }

    boolean dfs(TreeNode root, int sum, int value) {
        if (root == null) {
            return false;
        }
        int v = root.val + value;
        if (sum == v && root.left == null && root.right == null) {
            return true;
        }
        return dfs(root.left, sum, v) || dfs(root.right, sum, v);
    }

    public boolean hasPathSum2(TreeNode root, int sum) {
        if (root == null)
            return false;

        LinkedList<TreeNode> nodeStack = new LinkedList<>();
        LinkedList<Integer> sumStack = new LinkedList<>();
        nodeStack.add(root);
        sumStack.add(sum - root.val);

        TreeNode node;
        int currSum;
        while (!nodeStack.isEmpty()) {
            node = nodeStack.pollLast();
            currSum = sumStack.pollLast();
            if (node == null) {
                break;
            }
            if ((node.right == null) && (node.left == null) && (currSum == 0))
                return true;

            if (node.right != null) {
                nodeStack.add(node.right);
                sumStack.add(currSum - node.right.val);
            }
            if (node.left != null) {
                nodeStack.add(node.left);
                sumStack.add(currSum - node.left.val);
            }
        }
        return false;
    }


    /**
     * 路径总和 III
     */
    public int pathSum3(TreeNode root, int sum) {
        if (root == null)
            return 0;
        LinkedList<TreeNode> nodeStack = new LinkedList<>();
        LinkedList<List<Integer>> sumStack = new LinkedList<>();
        nodeStack.add(root);
        sumStack.add(Arrays.asList(sum - root.val));
        int res = sum - root.val == 0 ? 1 : 0;

        while (!nodeStack.isEmpty()) {
            TreeNode node = nodeStack.pollLast();
            List<Integer> currSum = sumStack.pollLast();
            if (node == null) {
                break;
            }
            List<Integer> left = new ArrayList<>(), right = new ArrayList<>();
            for (Integer integer : currSum) {
                if (node.right != null) {
                    right.add(integer - node.right.val);
                    res += integer - node.right.val == 0 ? 1 : 0;
                }
                if (node.left != null) {
                    left.add(integer - node.left.val);
                    res += integer - node.left.val == 0 ? 1 : 0;
                }
            }
            if (node.left != null) {
                left.add(sum - node.left.val);
                nodeStack.add(node.left);
                sumStack.add(left);
                res += sum - node.left.val == 0 ? 1 : 0;
            }
            if (node.right != null) {
                right.add(sum - node.right.val);
                nodeStack.add(node.right);
                sumStack.add(right);
                res += sum - node.right.val == 0 ? 1 : 0;
            }
        }
        return res;
    }

    public int pathSum2(TreeNode root, int sum) {
        if (root == null)
            return 0;
        LinkedList<TreeNode> nodeStack = new LinkedList<>();
        LinkedList<TreeNode> tmp = new LinkedList<>();
        LinkedList<Integer> sumStack = new LinkedList<>();
        nodeStack.add(root);
        sumStack.add(sum - root.val);
        tmp.add(root);
        while (!tmp.isEmpty()) {
            TreeNode node = tmp.pollLast();
            if (node == null) {
                break;
            }
            if (node.right != null) {
                nodeStack.add(node.right);
                sumStack.add(sum - node.right.val);
                tmp.add(node.right);
            }
            if (node.left != null) {
                nodeStack.add(node.left);
                sumStack.add(sum - node.left.val);
                tmp.add(node.left);
            }
        }
        int count = 0;
        while (!nodeStack.isEmpty()) {
            TreeNode node = nodeStack.pollLast();
            int currSum = sumStack.pollLast();
            if (node == null) {
                break;
            }
            if ((currSum == 0)) {
                count++;
            }

            if (node.right != null) {
                nodeStack.add(node.right);
                sumStack.add(currSum - node.right.val);
            }
            if (node.left != null) {
                nodeStack.add(node.left);
                sumStack.add(currSum - node.left.val);
            }
        }
        return count;
    }

    public int pathSum(TreeNode root, int sum) {
        return pathSum(root, sum, new int[1000], 0);
    }

    public int pathSum(TreeNode root, int sum, int[] array/*保存路径*/, int p/*指向路径终点*/) {
        if (root == null) {
            return 0;
        }
        int tmp = root.val;
        int n = root.val == sum ? 1 : 0;
        for (int i = p - 1; i >= 0; i--) {
            tmp += array[i];
            if (tmp == sum) {
                n++;
            }
        }
        array[p] = root.val;
        int n1 = pathSum(root.left, sum, array, p + 1);
        int n2 = pathSum(root.right, sum, array, p + 1);
        return n + n1 + n2;
    }

    /**
     * 二叉搜索树的最近公共祖先
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode node = root;

        while (node != null) {
            if (p.val > node.val && q.val > node.val) {
                // 如果p和q的值，大于当前节点值，则取右子节点
                node = node.right;
            } else if (p.val < node.val && q.val < node.val) {
                // 如果p和q的值，小于当前节点值，则取左子节点
                node = node.left;
            } else {
                return node;
            }
        }
        return null;
    }

    /**
     * 给定一个二叉树，判断它是否是高度平衡的二叉树。
     * 本题中，一棵高度平衡二叉树定义为：
     * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
     */
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

    /**
     * 有序链表转换二叉搜索树
     * 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
     * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
     */
    public TreeNode sortedListToBST(ListNode head) {
        int length = getLength(head);
        return (TreeNode) buildTree(0, length - 1, head)[0];
    }

    public int getLength(ListNode head) {
        int ret = 0;
        while (head != null) {
            ++ret;
            head = head.next;
        }
        return ret;
    }

    public Object[] buildTree(int left, int right, ListNode head) {
        if (left > right) {
            return new Object[]{null, head};
        }
        int mid = (left + right + 1) / 2;
        TreeNode root = new TreeNode();
        Object[] res = buildTree(left, mid - 1, head);
        root.left = (TreeNode) res[0];
        head = (ListNode) res[1];
        root.val = head.val;
        head = head.next;
        res = buildTree(mid + 1, right, head);
        root.right = (TreeNode) res[0];
        return new Object[]{root, res[1]};
    }
}